public class PriorityQueue {
    public int[] elem;
    public int usedSize;
    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    public PriorityQueue() {
        this.elem = new int[DEFAULT_CAPACITY];
        this.usedSize = 0;
    }

    /**
     * 建堆的时间复杂度：O(n)
     * 从最后一个非叶子节点开始，依次向下调整
     * @param array 用于构建堆的数组
     */
    public void createHeap(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        
        // 确保数组容量足够
        if (array.length > elem.length) {
            elem = new int[array.length];
        }
        
        // 复制数组元素
        System.arraycopy(array, 0, elem, 0, array.length);
        usedSize = array.length;
        
        // 从最后一个非叶子节点开始向下调整
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整算法，用于维护大根堆性质
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root, int len) {
        int parent = root;
        int child = 2 * parent + 1; // 左孩子
        
        while (child < len) {
            // 比较左右孩子，取较大值的下标
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            
            // 如果孩子大于父亲，则交换
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                
                // 继续向下调整
                parent = child;
                child = 2 * parent + 1;
            } else {
                // 不需要调整，直接退出
                break;
            }
        }
    }


    /**
     * 入队：添加元素并保持大根堆性质
     * @param val 要添加的元素
     */
    public void push(int val) {
        if (isFull()) {
            // 扩容操作，扩容为原来的1.5倍
            elem = java.util.Arrays.copyOf(elem, elem.length * 3 / 2);
        }
        
        elem[usedSize] = val;
        usedSize++;
        
        // 向上调整，保持大根堆
        shiftUp(usedSize - 1);
    }

    /**
     * 向上调整算法，用于插入元素后维护大根堆性质
     * @param child 新插入元素的下标
     */
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        
        while (child > 0) {
            // 如果孩子大于父亲，则交换
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                
                // 继续向上调整
                child = parent;
                parent = (child - 1) / 2;
            } else {
                // 不需要调整，直接退出
                break;
            }
        }
    }

    /**
     * 判断堆是否已满
     * @return 堆满返回true，否则返回false
     */
    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 出队【删除】：删除堆顶元素（优先级最高的元素）
     * 并保持大根堆性质
     */
    public void pollHeap() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("堆为空，无法删除元素");
        }
        
        // 交换堆顶元素和最后一个元素
        int temp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] = temp;
        
        usedSize--;
        
        // 向下调整堆顶元素
        shiftDown(0, usedSize);
    }

    /**
     * 判断堆是否为空
     * @return 堆空返回true，否则返回false
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取堆顶元素（优先级最高的元素）
     * @return 堆顶元素的值
     */
    public int peekHeap() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("堆为空，无法获取堆顶元素");
        }
        return elem[0];
    }
}